{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# Minimum Eigen Optimizer\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Introduction"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "An interesting class of optimization problems to be addressed by quantum computing are Quadratic Unconstrained Binary Optimization (QUBO) problems.\n",
    "Finding the solution to a QUBO is equivalent to finding the ground state of a corresponding Ising Hamiltonian, which is an important problem not only in optimization, but also in quantum chemistry and physics. For this translation, the binary variables taking values in $\\{0, 1\\}$ are replaced by spin variables taking values in $\\{-1, +1\\}$, which allows to replace the resulting spin variables by Pauli Z matrices, and thus, an Ising Hamiltonian. For more details on this mapping we refer to [1].\n",
    "\n",
    "Qiskit provides automatic conversion from a suitable `QuadraticProgram` to an Ising Hamiltonian, which then allows to leverage all the `MinimumEigenSolver` such as\n",
    "- `VQE`,\n",
    "- `QAOA`, or\n",
    "- `NumpyMinimumEigensolver` (classical exact method).\n",
    "\n",
    "Qiskit wraps the translation to an Ising Hamiltonian (in Qiskit Aqua also called `Operator`), the call to an `MinimumEigensolver` as well as the translation of the results back to `OptimizationResult` in the `MinimumEigenOptimizer`.\n",
    "\n",
    "In the following we first illustrate the conversion from a `QuadraticProgram` to an `Operator` and then show how to use the `MinimumEigenOptimizer` with different `MinimumEigensolver` to solve a given `QuadraticProgram`.\n",
    "The algorithms in Qiskit automatically try to convert a given problem to the supported problem class if possible, for instance, the `MinimumEigenOptimizer` will automatically translate integer variables to binary variables or add a linear equality constraints as a quadratic penalty term to the objective. It should be mentioned that Aqua will through a `QiskitOptimizationError` if conversion of a quadratic program with integer variable is attempted.\n",
    "\n",
    "The circuit depth of `QAOA` potentially has to be increased with the problem size, which might be prohibitive for near-term quantum devices.\n",
    "A possible workaround is Recursive QAOA, as introduced in [2].\n",
    "Qiskit generalizes this concept to the `RecursiveMinimumEigenOptimizer`, which is introduced at the end of this tutorial.\n",
    "\n",
    "### References\n",
    "[1] [A. Lucas, *Ising formulations of many NP problems,* Front. Phys., 12 (2014).](https://arxiv.org/abs/1302.5843)\n",
    "\n",
    "[2] [S. Bravyi, A. Kliesch, R. Koenig, E. Tang, *Obstacles to State Preparation and Variational Optimization from Symmetry Protection,* arXiv  preprint arXiv:1910.08980 (2019).](https://arxiv.org/abs/1910.08980)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Converting a QUBO to an Operator"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 1,
   "metadata": {},
   "outputs": [],
   "source": [
    "from qiskit import BasicAer\n",
    "from qiskit.aqua import aqua_globals, QuantumInstance\n",
    "from qiskit.aqua.algorithms import QAOA, NumPyMinimumEigensolver\n",
    "from qiskit.optimization.algorithms import MinimumEigenOptimizer, RecursiveMinimumEigenOptimizer\n",
    "from qiskit.optimization import QuadraticProgram"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 2,
   "metadata": {
    "scrolled": true,
    "tags": []
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "\\ This file has been generated by DOcplex\n",
      "\\ ENCODING=ISO-8859-1\n",
      "\\Problem name: CPLEX\n",
      "\n",
      "Minimize\n",
      " obj: x - 2 y + 3 z + [ 2 x*y - 2 x*z + 4 y*z ]/2\n",
      "Subject To\n",
      "\n",
      "Bounds\n",
      " 0 <= x <= 1\n",
      " 0 <= y <= 1\n",
      " 0 <= z <= 1\n",
      "\n",
      "Binaries\n",
      " x y z\n",
      "End\n",
      "\n"
     ]
    }
   ],
   "source": [
    "# create a QUBO\n",
    "qubo = QuadraticProgram()\n",
    "qubo.binary_var('x')\n",
    "qubo.binary_var('y')\n",
    "qubo.binary_var('z')\n",
    "qubo.minimize(linear=[1,-2,3], quadratic={('x', 'y'): 1, ('x', 'z'): -1, ('y', 'z'): 2})\n",
    "print(qubo.export_as_lp_string())"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Next we translate this QUBO into an Ising operator. This results not only in an `Operator` but also in a constant offset to be taking into account to shift the resulting value."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 3,
   "metadata": {
    "tags": []
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "offset: 1.5\n",
      "operator:\n",
      "SummedOp([\n",
      "  -0.5 * IIZ,\n",
      "  0.25 * IZI,\n",
      "  -1.75 * ZII,\n",
      "  0.25 * IZZ,\n",
      "  -0.25 * ZIZ,\n",
      "  0.5 * ZZI\n",
      "])\n"
     ]
    }
   ],
   "source": [
    "op, offset = qubo.to_ising()\n",
    "print('offset: {}'.format(offset))\n",
    "print('operator:')\n",
    "print(op)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Sometimes an `QuadraticProgram` might also directly be given in the form of an `Operator`. For such cases, Qiskit also provides a converter from an `Operator` back to a `QuadraticProgram`, which we illustrate in the following."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 4,
   "metadata": {
    "tags": []
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "\\ This file has been generated by DOcplex\n",
      "\\ ENCODING=ISO-8859-1\n",
      "\\Problem name: CPLEX\n",
      "\n",
      "Minimize\n",
      " obj: x_0 - 2 x_1 + 3 x_2 + [ 2 x_0*x_1 - 2 x_0*x_2 + 4 x_1*x_2 ]/2\n",
      "Subject To\n",
      "\n",
      "Bounds\n",
      " 0 <= x_0 <= 1\n",
      " 0 <= x_1 <= 1\n",
      " 0 <= x_2 <= 1\n",
      "\n",
      "Binaries\n",
      " x_0 x_1 x_2\n",
      "End\n",
      "\n"
     ]
    }
   ],
   "source": [
    "qp=QuadraticProgram()\n",
    "qp.from_ising(op, offset, linear=True)\n",
    "print(qp.export_as_lp_string())"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "This converter allows, for instance, to translate an `Operator` to a `QuadraticProgram` and then solve the problem with other algorithms that are not based on the Ising Hamiltonian representation, such as the `GroverOptimizer`."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Solving a QUBO with the MinimumEigenOptimizer"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "We start by initializing the `MinimumEigensolver` we want to use."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 5,
   "metadata": {},
   "outputs": [],
   "source": [
    "aqua_globals.random_seed = 10598\n",
    "quantum_instance = QuantumInstance(BasicAer.get_backend('statevector_simulator'),\n",
    "                                   seed_simulator=aqua_globals.random_seed,\n",
    "                                   seed_transpiler=aqua_globals.random_seed)\n",
    "qaoa_mes = QAOA(quantum_instance=quantum_instance, initial_point=[0., 0.])\n",
    "exact_mes = NumPyMinimumEigensolver()"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Then, we use the `MinimumEigensolver` to create `MinimumEigenOptimizer`."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 6,
   "metadata": {},
   "outputs": [],
   "source": [
    "qaoa = MinimumEigenOptimizer(qaoa_mes)   # using QAOA\n",
    "exact = MinimumEigenOptimizer(exact_mes)  # using the exact classical numpy minimum eigen solver"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "We first use the `MinimumEigenOptimizer` based on the classical exact `NumPyMinimumEigensolver` to get the optimal benchmark solution for this small example."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 7,
   "metadata": {
    "tags": []
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "optimal function value: -2.0\n",
      "optimal value: [0. 1. 0.]\n",
      "status: SUCCESS\n"
     ]
    }
   ],
   "source": [
    "exact_result = exact.solve(qubo)\n",
    "print(exact_result)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Next we apply the `MinimumEigenOptimizer` based on `QAOA` to the same problem."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 8,
   "metadata": {
    "tags": []
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "optimal function value: -2.0\n",
      "optimal value: [0. 1. 0.]\n",
      "status: SUCCESS\n"
     ]
    }
   ],
   "source": [
    "qaoa_result = qaoa.solve(qubo)\n",
    "print(qaoa_result)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## RecursiveMinimumEigenOptimizer"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "The `RecursiveMinimumEigenOptimizer` takes a `MinimumEigenOptimizer` as input and applies the recursive optimization scheme to reduce the size of the problem one variable at a time.\n",
    "Once the size of the generated intermediate problem is below a given threshold (`min_num_vars`), the `RecursiveMinimumEigenOptimizer` uses another solver (`min_num_vars_optimizer`), e.g., an exact classical solver such as CPLEX or the `MinimumEigenOptimizer` based on the `NumPyMinimumEigensolver`.\n",
    "\n",
    "In the following, we show how to use the `RecursiveMinimumEigenOptimizer` using the two `MinimumEigenOptimizer` introduced before."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "First, we construct the `RecursiveMinimumEigenOptimizer` such that it reduces the problem size from 3 variables to 1 variable and then uses the exact solver for the last variable. Then we call `solve` to optimize the considered problem."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 9,
   "metadata": {},
   "outputs": [],
   "source": [
    "rqaoa = RecursiveMinimumEigenOptimizer(min_eigen_optimizer=qaoa, min_num_vars=1, min_num_vars_optimizer=exact)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 10,
   "metadata": {
    "tags": []
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "optimal function value: -2.0\n",
      "optimal value: [0. 1. 0.]\n",
      "status: SUCCESS\n"
     ]
    }
   ],
   "source": [
    "rqaoa_result = rqaoa.solve(qubo)\n",
    "print(rqaoa_result)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 11,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/html": [
       "<h3>Version Information</h3><table><tr><th>Qiskit Software</th><th>Version</th></tr><tr><td>Qiskit</td><td>None</td></tr><tr><td>Terra</td><td>0.16.0</td></tr><tr><td>Aer</td><td>0.7.0</td></tr><tr><td>Ignis</td><td>0.5.0</td></tr><tr><td>Aqua</td><td>0.8.1</td></tr><tr><td>IBM Q Provider</td><td>0.10.0</td></tr><tr><th>System information</th></tr><tr><td>Python</td><td>3.7.4 (default, Aug 13 2019, 15:17:50) \n",
       "[Clang 4.0.1 (tags/RELEASE_401/final)]</td></tr><tr><td>OS</td><td>Darwin</td></tr><tr><td>CPUs</td><td>2</td></tr><tr><td>Memory (Gb)</td><td>12.0</td></tr><tr><td colspan='2'>Wed Nov 11 11:22:40 2020 EST</td></tr></table>"
      ],
      "text/plain": [
       "<IPython.core.display.HTML object>"
      ]
     },
     "metadata": {},
     "output_type": "display_data"
    },
    {
     "data": {
      "text/html": [
       "<div style='width: 100%; background-color:#d5d9e0;padding-left: 10px; padding-bottom: 10px; padding-right: 10px; padding-top: 5px'><h3>This code is a part of Qiskit</h3><p>&copy; Copyright IBM 2017, 2020.</p><p>This code is licensed under the Apache License, Version 2.0. You may<br>obtain a copy of this license in the LICENSE.txt file in the root directory<br> of this source tree or at http://www.apache.org/licenses/LICENSE-2.0.<p>Any modifications or derivative works of this code must retain this<br>copyright notice, and modified files need to carry a notice indicating<br>that they have been altered from the originals.</p></div>"
      ],
      "text/plain": [
       "<IPython.core.display.HTML object>"
      ]
     },
     "metadata": {},
     "output_type": "display_data"
    }
   ],
   "source": [
    "import qiskit.tools.jupyter\n",
    "%qiskit_version_table\n",
    "%qiskit_copyright"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": []
  }
 ],
 "metadata": {
  "kernelspec": {
   "display_name": "Python 3",
   "language": "python",
   "name": "python3"
  },
  "language_info": {
   "codemirror_mode": {
    "name": "ipython",
    "version": 3
   },
   "file_extension": ".py",
   "mimetype": "text/x-python",
   "name": "python",
   "nbconvert_exporter": "python",
   "pygments_lexer": "ipython3",
   "version": "3.7.4"
  },
  "toc": {
   "base_numbering": 1,
   "nav_menu": {},
   "number_sections": true,
   "sideBar": true,
   "skip_h1_title": false,
   "title_cell": "Table of Contents",
   "title_sidebar": "Contents",
   "toc_cell": false,
   "toc_position": {},
   "toc_section_display": true,
   "toc_window_display": false
  }
 },
 "nbformat": 4,
 "nbformat_minor": 2
}
